class Solution:
    def longestIncreasingPath(self, matrix) -> int:
        xLen = len(matrix)
        if xLen == 0:
            return 0
        yLen = len(matrix[0])
        if yLen == 0:
            return 0
        minSet = set()
        for i in range(xLen):
            for j in range(yLen):
                zeroDegree = True
                for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
                    if 0 <= x < xLen and 0 <= y < yLen:
                        if matrix[x][y] < matrix[i][j]:
                            zeroDegree = False
                            break
                if zeroDegree:
                    minSet.add((i, j))
        maxLen = 0
        cache = [[1 if (x, y) in minSet else None for y in range(yLen)] for x in range(xLen)]
        # print(cache)
        for i in range(xLen):
            for j in range(yLen):
                maxLen = max(maxLen, self.longestOne(i, j, cache, xLen, yLen, matrix))
        return maxLen

    def longestOne(self, i, j, cache, xLen, yLen,matrix):
        if not(0 <= i < xLen and 0 <= j < yLen):
            return 0
        if cache[i][j] is not None:
            return cache[i][j]
        maxDegree = 0
        for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
            if 0 <= x < xLen and 0 <= y < yLen and matrix[x][y] < matrix[i][j]:
                maxDegree = max(maxDegree, self.longestOne(x, y, cache, xLen, yLen, matrix)+1)
        cache[i][j] = maxDegree
        return maxDegree

if __name__ == '__main__':
    so = Solution()
    nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]
    r = so.longestIncreasingPath(nums)
    print(r)
